package sort;

import java.util.Random;

/**
 * @Auther: MFM
 * @Date: 2022/3/20 - 03 - 20 - 15:05
 * @version: 1.0
 */

public class selectionSort {
    //简单选择排序
    public void selectSort(int[] arr){
        if (arr == null){
            return;
        }

        //将所有的数遍历并排放
        for (int i = 0; i <arr.length ; i++) {
            //存放最小数的索引
            int minNum = i;
            //遍历出最小的数的索引
            for (int j = i; j < arr.length; j++) {
                if (arr[j]<arr[minNum]){
                    minNum = j;
                }
            }

            //交换最小数和已排序后一位
            new ChangeSort().change(arr,minNum,i);
        }

    }

    public void heapSort(int[] arr){
        //将arr作为待排序数组 (arr.length-1)/2 为最后一个非叶子节点 并从后往前开始调整 arr.length 要对数组中所有元素进行调整
        heapSort(arr,(arr.length-1-1)/2,arr.length);
    }

    /**
     * 将无序数组转换为大根堆
     * @param arr 需要转换的无序数组
     * @param i   从哪一个非叶子节点开始调整
     * @param n   对多少元素进行调整
     */
    public void heapSort(int[] arr,int i,int n){
        int count = n;
        for (int k = 0; k < n-1; k++) {
            for (int j = i; j >= 0; j--) {
                maxInRoot(arr,j,count);
            }

            new ChangeSort().change(arr,0,count-1);
            count--;
        }
    }

    /**
     * 找出 以i为根的最小树中的最大值
     * @param arr   转化为数的数组
     * @param i     当前根
     */
    public void maxInRoot(int[] arr,int i,int n){
        int kidL = 0;
        int kidR = 0;
        if ( 2 * i + 2 < n){
            kidL = 2 * i + 1;
            kidR = 2 * i + 2;
        }
        if ( 2 * i + 1 < n){
            kidL = 2 * i + 1;
        }




        if (kidL !=0 && arr[kidL] > arr[i] ){
            int num = arr[kidL];
            arr[kidL] = arr[i];
            arr[i] = num;
        }
        if (kidR !=0 && arr[kidR] > arr[i]){
            int num = arr[kidR];
            arr[kidR] = arr[i];
            arr[i] = num;
        }
    }

    public static void main(String[] args) {
        /*
         * 测试结果
         * 1000000 排序所用时间为
         * 简单选择排序 1min+
         * 堆排序  1min+
         * */
        int[] arr = new int[1000000];
        Random r = new Random();


        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }

        long start = System.currentTimeMillis();

        new selectionSort().heapSort(arr);

        long end = System.currentTimeMillis();

        System.out.println(end - start);
//        int[] arr = {15,5,2,7,12,6,1,4,3,9,8};
//
//        new selectionSort().selectSort(arr);
//
//        for (int a : arr
//        ) {
//            System.out.print(a + " ");
//        }
    }
}
